#pragma once
int binSearch(int* arr, int b, int e, int val)
{
	int min = b, max = e, mid;
	while( min < max -1 )
	{
		mid = min + (max - min)/2;
		if( val <= arr[mid] )
			max = mid;
		else 
			min = mid;
	}

	if( arr[max] == val )
		return max;
	if( arr[min] == val )
		return min;
	else
		return -1;
}

int binSearch2(int* arr, int b, int e, int val)
{
	if(b == e || b == e -1)
	{
		if( arr[b] == val )
			return b;
		else if ( arr[e] == val )
			return e;
		else
			return -1;
	}

	int mid = b + ( e - b )/2;
	if( val <= arr[mid] )
	{
		return binSearch2(arr, b, mid, val);
	}
	else
	{
		return binSearch2(arr, mid, e, val); 
	}
}

void __bin_count(int* arr, int lo, int hi, int val, int& count);

int bin_count( int* arr, int n, int val)
{
	int count = 0;
	__bin_count(arr, 0, n-1, val, count);
	return count;
}
void __bin_count(int* arr, int lo, int hi, int val, int& count)
{
	if( arr == 0 ) return;  //Invalid input
	
	if( hi < lo ) return;
	if( arr[lo] == val && arr[hi] == val )
	{
		count += hi - lo + 1;
		return;
	}
		
	int mid = lo + (hi - lo)/2;
	
	if( arr[mid] > val )		//discard the up half, arr[mid~] > val 
		__bin_count(arr, lo, mid -1, val, count);
	else if( arr[mid] < val )   //discard the lower half, arr[~mid] < val   
		__bin_count(arr, mid+1, hi, val, count);
	else // if( arr[mid] == val )
	{
		if( arr[hi] != val && arr[lo] != val)  //Worst case, need to search both sections
		{
			__bin_count(arr, lo, mid, val, count);
			__bin_count(arr, mid+1, hi, val, count);
		}
		else
		{
			if( arr[lo] == val )
			{
				count += mid - lo + 1;
				__bin_count(arr, mid+1, hi, val, count);
			}				
			else if( arr[hi] == val )
			{
				count += hi -mid + 1;
				__bin_count(arr, lo, mid-1, val, count);
			}
		}
	}
}